class Solution {
public:
    typedef struct ListNode* Node;
    Node midNode(ListNode* head)
    {
        Node fast=head;
        Node slow=head;
        while(fast->next && fast->next->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }

    Node reverseNode(ListNode* head)
    {
        Node pre=nullptr;
        Node cur=head;
        while(cur)
        {
            Node temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        Node p1=head;
        Node p2=reverseNode(midNode(head));
        while(p1)
        {
            if(p1->val!=p2->val) return false;
            p1=p1->next;
            p2=p2->next;
        }
        return true;
    }
};
